class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        path = []
        direction = 1
        queue = collections.deque()
        if root == None:
            return []
        
        queue.append(root)
        while len(queue) > 0:
            cur_path = []
            for i in range(len(queue)):
                node = queue.popleft()
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
                
                #判断插入顺序
                if direction == 1:
                    cur_path.append(node.val)
                else:
                    cur_path.insert(0, node.val)
            direction = direction * -1
            path.append(cur_path)
        return path
